package leetcode.editor.cn;

//[72]编辑距离
public class EditDistance72 {
    public static void main(String[] args) {
        Solution solution = new EditDistance72().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        //  72 编辑距离
        //  链接：https://leetcode.cn/problems/edit-distance/solution/bian-ji-ju-chi-by-leetcode-solution/
        //
        //一共 3 中操作
        // 本质不同的操作实际上只有三种：
        // A add == B del
        // A del == B add
        // A replace == B replace
        //在单词 A 中插入一个字符；
        //在单词 B 中插入一个字符；
        //修改单词 A 的一个字符。
        public int minDistance(String w1, String w2) {
            //chech
            if (w1 == null || w1.length() == 0) {
                return w2 == null ? 0 : w2.length();
            }
            if (w2 == null || w2.length() == 0) {
                return 0;
            }

            //init dp
            int len1 = w1.length();
            int len2 = w2.length();
            //dp 定义 dp[i,j]  w1 前 i 字符==》w2前 j 个字符最小步数。
            int[][] dp = new int[len1 + 1][len2 + 1];
            for (int i = 0; i < len1 + 1; i++) {
                dp[i][0] = i;
            }
            for (int i = 0; i < len2 + 1; i++) {
                dp[0][i] = i;
            }

            //dp 方程
            //dp[i,j]= if wi=wj   dp[i-1,j-1]
            //         else  min dp[i-1,j-1] +1  replace
            //                  dp[i-1,j] +1  insert
            //                  dp[i,j-1] +1  del  这 2 个可以互换
            for (int i = 1; i < len1+1; i++) {
                //TODO  len1+1 因为 i-1 是比较的 0 个，得出的第 1 个，所以
                // i = len 比较的是 len-i 这个 index. dp[len]才是结果。
                for (int j = 1; j < len2+1; j++) {
                    //若 A 和 B 的最后一个字母 相同：
                    if (w1.charAt(i-1) == w2.charAt(j-1)) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        //不同
                        int a = dp[i - 1][j - 1] + 1;
                        int b = dp[i - 1][j] + 1;
                        int c = dp[i][j - 1] + 1;
                        dp[i][j] = Math.min(a, Math.min(b, c));
                    }
                }
            }
            return dp[len1][len2];
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}